#include <iostream>
using namespace std; 
#include <vector>
#include <stack>

vector<vector<int>> MonotonicStack(vector<int>& arr);

vector<vector<int>> MonotonicStack(vector<int>& arr)
{
  int N = static_cast<int>(arr.size());
  vector<vector<int>> ans(N , vector<int>(2 , -1));
  stack<int> st;

  for (int i = 0; i < N; i++)
  {
    while(!st.empty() && arr[st.top()] > arr[i])
    {
      int PopIndex = st.top();
      st.pop();

      int LeftIndex = st.empty() ? -1 : st.top();

      ans[PopIndex][0] = LeftIndex;
      ans[PopIndex][1] = i;
    }

    st.push(i);
  }

  // 此时栈中还有剩余元素未清空
  while (!st.empty())
  {
    int PopIndex = st.top();
    st.pop();

    int LeftIndex = st.empty()? -1 : st.top();

    ans[PopIndex][0] = LeftIndex;
    ans[PopIndex][1] = -1; // 这里也可以不写 因为本来就是-1
  }

  return ans;
}





int main()
{
  vector<int> arr = {1 , 4 , 2, 5 ,7};
  vector<vector<int>> ans = MonotonicStack(arr);
  for(auto x : ans)
  {
    for (auto y: x)
    {
      cout << y << " ";
    }
    cout << endl;
  }

  for (auto x : arr)
  {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}
